# -*- coding: utf-8 -*-
import random;

# 实现 pow(x, n) ，即计算 x 的 n 次幂函数

# 示例 1:
# 输入: 2.00000, 10
# 输出: 1024.00000

# 示例 2:
# 输入: 2.10000, 3
# 输出: 9.26100

# 示例 3:
# 输入: 2.00000, -2
# 输出: 0.25000
# 解释: 2-2 = 1/22 = 1/4 = 0.25

# 说明:
# -100.0 < x < 100.0
# n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]

# class Solution(object):
#     def myPow(self, x, n):
#         """
#         :type x: float
#         :type n: int
#         :rtype: float
#         """
#         rtn = 1;

#         times = abs(n);
#         signal = 1;
#         signal_mul = x;

#         while times > 0:
#             if times - signal < 0:
#                 signal = 1;
#                 signal_mul = x;

#             rtn *= signal_mul;
#             times -= signal;

#             signal += signal;
#             signal_mul *= signal_mul;

#         if n < 0:
#             return 1 / rtn;
#         else:
#             return rtn;









# 官方解决方案，同上，但是书写方式更简单
# 算法说明:
# 算法的重点主要在于n的拆解上
# 把n拆解为二进制数
# 如 18 拆解为二进制为 10010
# 辗转相除步骤如下
# 剩余    商    余数
# 18     9     0
# 9      4     1
# 4      2     0
# 2      1     0
# 1      0     1
# 2^4 + 2^1 = 18
# 根据以上思路
# 只要在2^1出现时构造出x^2
# 在2^4出现的时候构造出x^16
# 即能解决问题

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            n = -n;
            x = 1 / x;

        rtn = 1;
        # 相乘2^0次
        product = x;

        while n > 0:
            if n % 2 == 1:
                rtn *= product;

            n = n // 2;
            # 辗转相乘的次数m, 相乘的次数为2^m
            product *= product;

        return rtn;

t = Solution();
print t.myPow(2.00000, 10)

